package 剑指Offer._4150;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/11 16:06
 * 把数组排成最小的数
 * 算法：排序 + 字符串
 * 把两个数字变成字符串相加
 * 判断 a + b 和 b + a 的大小
 */
public class _45 {
    public static void main(String[] args) {
        int[] nums = {12, 121};
        System.out.println(new _45().minNumber(nums));
    }

    public String minNumber(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        String ans = "";
        for (int num : nums) ans += num;
        return ans;
    }

    void quickSort(int[] nums, int begin, int end) {
        if (begin >= end) return;
        int left = begin, right = end;
        while (left < right) {
            while (left < right && compare(nums[right], nums[begin])) --right;
            while (left < right && !compare(nums[left], nums[begin])) ++left;
            int tem = nums[left];
            nums[left] = nums[right];
            nums[right] = tem;
        }
        int tem = nums[begin];
        nums[begin] = nums[left];
        nums[left] = tem;
        quickSort(nums, begin, left - 1);
        quickSort(nums, left + 1, end);
    }

    boolean compare(int num1, int num2) {
        String a = num1 + "" + num2;
        String b = num2 + "" + num1;
        int len = a.length();
        for (int i = 0; i < len; i++) {
            char c1 = a.charAt(i), c2 = b.charAt(i);
            if (c1 > c2) return true;
            else if (c1 < c2) return false;
        }
        return a.charAt(len - 1) >= b.charAt(len - 1);
    }

}
